Pencarian Lawan dan Pemenuhan Kendala

Selamat datang di Pelajaran 3 dari Konsep Kecerdasan Buatan (PolyU COMP5511). Dalam sesi ini, kita beralih dari pencarian jalur agen tunggal ke Pencarian Lawan, di mana agen beroperasi di lingkungan multi-agen yang kompetitif. Kami juga memperkenalkan Masalah Pemenuhan Kendala (CSPs), sebuah paradigma di mana tujuannya adalah untuk menemukan status yang memenuhi seperangkat batasan tertentu daripada jalur.

Konsep Inti

Pencarian Lawan: Berfokus pada algoritma seperti Minimax dan Pruning Alpha-Beta untuk membuat keputusan rasional melawan lawan yang cerdas.
Pencarian Pohon Monte Carlo (MCTS): Menjelajahi pengambilan keputusan probabilistik, berfungsi sebagai tulang punggung AI game modern seperti AlphaGo.
Pemenuhan Kendala: Memodelkan masalah menggunakan Variabel, Domain, dan Kendala, diselesaikan melalui Backtracking dan Pencarian Lokal.

Analisis Kompleksitas

Dalam pengaturan lawan, kompleksitas ruang pencarian sering ditentukan oleh faktor percabangan permainan $b$ dan kedalaman $d$ , yang mengarah pada biaya komputasi: $O (b^{d})$ Pertumbuhan eksponensial ini memerlukan strategi pemangkasan yang efisien seperti Pruning Alpha-Beta.

Peringatan Pergeseran Paradigma

Berbeda dengan pencarian standar (misalnya, A* atau BFS) di mana lingkungan bersifat statis, Pencarian Lawan mengasumsikan lingkungan (lawan) secara aktif mencoba meminimalkan kesuksesan Anda. Dalam CSPs, urutan tindakan kurang penting daripada validitas penetapan akhir.

Pseudokode Konseptual: Tipe Agen

# Adversarial Agent (Game Theory)
functionDecide_Move(state):
returnMaximize_Utility(Predict_Opponent_Minimization(state))
# CSP Solver (Constraint Logic)
functionSolve_CSP(variables, constraints):
ifAll_Constraints_Satisfied(assignment):
returnassignment
else:
returnBacktrack_Search(variables)

Course Roadmap

Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).